package org.example.likou150.stack;





import java.util.*;
//https://leetcode.cn/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150
public class MinStack {
    public static void main(String[] args) {
        MinStack minStack=new MinStack();
        minStack.push(2);
        minStack.push(0);
        minStack.push(3);
        minStack.push(0);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        minStack.pop();
        System.out.println(minStack.getMin());
    }

    Node head;
    Node min;

    public MinStack() {
    }

    public void push(int val) {
        if(head==null){
            head=new Node(val, null,null);
            min=head;
        }else {
            Node node = new Node(val, null, head);
            head=node;
            Node temp = min;
            if(val <= min.getE()){
                node.setSort(min);
                min = node;
            }else{
                while (temp.getE()<val){
                    if(temp.getNext()==null){
                        break;
                    }
                    temp=temp.getNext();
                }
                temp.setSort(node);
            }
        }
    }

    public void pop() {
        Node preTemp=null;
        Node temp = min;
        while (head!=temp){
            preTemp=temp;
            temp=temp.getSort();
            if(temp==null){
                preTemp.setSort(null);
                break;
            }
        }
        if(temp==null){
            preTemp.setSort(null);
        }else if(preTemp==null){
            min = min.getSort();
        }else {
            preTemp.setSort(temp.getSort());
        }
        head=head.getNext();
    }

    public int top() {
        return head.getE();
    }

    public int getMin() {
        return min.getE();
    }

    private class Node{
    private Node next;
    private Node pre;
    private Node sort;
    private int e;

    public Node(int e, Node pre, Node next) {
        this.e = e;
        this.pre = pre;
        this.next = next;
    }


    public Node getSort() {
        return sort;
    }

    public void setSort(Node sort) {
        this.sort = sort;
    }

    public int getE() {
        return e;
    }


    public Node getNext() {
        return next;
    }
    }



//    List<Integer> stack = new ArrayList<>();
//    Map<Integer,Integer> treeMap = new TreeMap();
//
//    public MinStack() {
//
//    }
//
//    public void push(int val) {
//        stack.add(val);
//        if(treeMap.containsKey(val)){
//            treeMap.compute(val, (k, count) -> count + 1);
//        }else {
//            treeMap.put(val, 1);
//        }
//    }
//
//    public void pop() {
//        Integer e = stack.get(stack.size()-1);
//        stack.remove(stack.size()-1);
//        Integer count = treeMap.get(e);
//        if(count<=1){
//            treeMap.remove(e);
//        }else {
//            treeMap.put(e, count - 1);
//        }
//
//    }
//
//    public int top() {
//        return stack.get(stack.size()-1);
//    }
//
//    public int getMin() {
//        Iterator<Integer> iterator = treeMap.keySet().iterator();
//        return iterator.next();
//    }
}

//class Node{
//    private Node next;
//    private Node pre;
//    private Node sort;
//    private int e;
//
//    public Node(int e, Node pre, Node next) {
//        this.e = e;
//        this.pre = pre;
//        this.next = next;
//    }
//
//
//    public Node getSort() {
//        return sort;
//    }
//
//    public void setSort(Node sort) {
//        this.sort = sort;
//    }
//
//    public int getE() {
//        return e;
//    }
//
//    public void setE(int e) {
//        this.e = e;
//    }
//
//    public Node getNext() {
//        return next;
//    }
//
//    public void setNext(Node next) {
//        this.next = next;
//    }
//
//    public Node getPre() {
//        return pre;
//    }
//
//    public void setPre(Node pre) {
//        this.pre = pre;
//    }
//}
